package demo.practice.competition;

import java.util.HashSet;
import java.util.Set;

public class P1898 {
    /**
     * "qlevcvgzfpryiqlwy"
     * "qlecfqlw"
     * [12,5]
     *
     * @param args
     */


    public static void main(String[] args) {
        P1898 p1898 = new P1898();
        int i = p1898.maximumRemovals("qlevcvgzfpryiqlwy", "qlecfqlw", new int[]{12, 5});
        System.out.println(i);
    }

    public int maximumRemovals(String s, String p, int[] removable) {
        int max= removable.length-1;
        int min= 0;


        while (max >=min) {
            int mid = min + (max - min) / 2;
            Set<Integer> rm = new HashSet<>();
            for (int i = 0; i <= mid; i++) {
                rm.add(removable[i]);
            }
            if (check(s, p, rm)) {
                min = mid + 1;
            } else {

                max = mid;
                if(max==min)
                    break;
            }
        }

        return min;
    }


    private boolean check(String s, String p, Set<Integer> rm) {  //判断p 是s的子序列
        int j=0;
        for(int i=0;i<s.length();i++){
            if(rm.contains(i))
                continue;
            if(s.charAt(i)== p.charAt(j)){
                j++;
                if(j==p.length())
                    return true;
            }
        }
        return false;
    }
}
